This invention is related generally to the design of integrated circuit chips and, more particularly, to a method of matching sub-circuit patterns in a larger transistor-level circuit design for the purpose of timing analysis, electrical rules checking, noise analysis, test pattern generation, design verification and circuit optimization.
VLSI (Very Large Scale Integration) and ULSI (Ultra Large Scale Integration) chips involve a heavy commitment of computer resources to design, test and manufacture chips and systems that involve millions of circuits interconnected to each other. Because of the large number of transistors, it is no longer possible to perform this task manually. As a result, a new field referred to as Electronic Design Automation (EDA) has been developed over the last decades to address the complexity of this design process.
Much of the increase in the size of modern VLSI has been accomplished through levels of abstraction and reuse. Large designs commonly consist of pre designed logic functions called xe2x80x9ccellsxe2x80x9d. These cells are provided in a library complete with characterizations of their function, timing performance, layout characteristics etc. While this greatly facilitates ease of reuse, the dependence on pre characterization tends to come at a cost. The necessity of limiting the number of cells provided in a library to a manageable number limits the flexibility that a designer has with regard to circuit topologies, device sizes and layout choices. This generally manifests itself in a reduction in chip performance and density. For this reason, large portions of those designs most sensitive to performance and/or density considerations are still implemented at a lower level of abstraction. So-called custom logic is designed at the transistor rather than the cell-level which affords the designer much greater flexibility to tune the design to his/her application. In addition to being more labor intensive, this custom design style places an additional burden on the design tools.
Unlike a high-level abstraction, transistor-level designs require tools to infer functionality from connectivity. All circuit design analysis and verification tools require identification of sub-circuits from a flat (nonhierarchical) netlist. The task of EDA tools is compounded by a large number of circuit combinations and a need to understand many custom design styles. This need to identify sub-circuits from a sea of transistors motivates an invention for pattern matching which can identify groups of transistors for any transistor-level EDA tool.
Sub-Graph Isomorphism
Isomorphism is defined as having the xe2x80x9csame formxe2x80x9d or xe2x80x9csame shapexe2x80x9d. If two groups of elements are isomorphic, there is a one-to-one relationship between the elements of one group and the elements of another. Graph isomorphism signifies that two entire graphs are identical. Sub-graph isomorphism implies that there is a one-to-one relationship between each element of the sub-graph and one of the elements of the larger graph.
Sub-graph isomorphism is a technique that is used advantageously for pattern matching. Pattern matching in a transistor-level netlist implies that every instance of a pattern, consisting of a plurality of transistors, can be found in a larger transistor-level netlist. The pattern is represented as a sub-graph, while the larger transistor-level netlist is modeled as a graph. In the field of circuit design analysis and verification, sub-graph isomorphism implies that all the transistors and electrical net connections which are present in the sub-graph can be found in a larger circuit graph. Typically, a circuit designer attempts to localize specific sub-circuits, such as an inverter or a multiplexer, in a larger circuit design. These sub-circuits need to be found such that the VLSI or ULSI design can be correctly timed, analyzed for circuit noise, checked for compliance with electrical rules specifications, tested, and formally verified. This identification of sub-circuits in a larger transistor-level circuit design is sometimes referred to sub-circuit extraction.
By way of example of how the problem of pattern matching has been handled heretofore, there is shown in FIG. 1 an inverter pattern 102 integral to a larger circuit design 104. There is one instance of the pattern in the larger circuit design. The match can be seen as follows:
In an exact pattern-matching, a pattern instance in the circuit design can only be identified as such if it precisely matches the specification of the pattern. The pattern instance will be missed by the pattern matcher if inputs are attached to Vdd or GND, or if inputs are shorted together. If any modification exists, the instance will not be recognized by the pattern matcher. Inexact pattern matching, on the other hand, implies that the instance can be recognized even if certain modifications are made in the imbedding of the pattern in the larger transistor-level netlist. Common modifications made by circuit designers include attaching inputs to Vdd or GND and shorting together of inputs. Only an inexact pattern matcher is able to identify such pattern instantiations.
In an inexact pattern-matching, the constraints for isomorphism are relaxed at the pattern external (boundary) net connections such that external nets in the pattern instance can be connected to special nets, such as Vdd or GND, or shorted to other external nets. Inexact sub-graph isomorphism is critical in transistor pattern-matching because, heretofore, users were required to specify a potentially exponential number of exact patterns in order to find all possible combinations of external connectivity.
The difficulties encountered by circuit designers who employ a prior art pattern matcher will be better understood with reference to the 3-input multiplexers illustrated in FIG. 2. Therein are shown fourteen patterns that are typically required to enumerate all possible combinations of external net connectivity of the 3-input multiplexer. The fourteen patterns capture all possible combinations of inputs attached to Vdd, to GND, and shorted together. Practitioners in the art will readily realize that, in the prior art, the number of patterns required grows exponentially with the number of inputs.
An effective way of avoiding the enumeration of exact patterns has not been identified up to now. Thus, circuit designers spend countless hours enumerating patterns and manually ensuring that they identified all external net configurations that are present in their design. Circuit designers called a pattern matcher for each of the thirteen possible modified patterns in order to find all instances of the general pattern referenced by FIG. 2 numeral 1 in their circuit design. Missed pattern instances due to a failure to identify all of the external net configurations lead to transistor-level timing errors, design verification errors, errors in circuit test pattern generation, and errors in electrical rules checking, resulting in a significant loss of functionality and slowing down many of the steps required to bring a circuit design to market.
Graph isomorphism techniques have been used for transistor-level netlist comparison in the past. Corneil""s graph labeling algorithm, described in xe2x80x9cRecent Results on the Graph Isomorphism Problemxe2x80x9d, Proc. Eighth Manitoba Conference on Numerical Mathematics and Computing, 1978, pp.13-31, is well-known and is the initial work on graph labeling using matched neighbors. Applications of Corneil""s graph isomorphism algorithm and graph coloring for graph isomorphism are described in U.S. Pat. No. 6,009,252 to Lipton entitled xe2x80x9cMethods, apparatus, and computer program products for determining equivalencies between integrated circuit schematics and layouts using color symmetrizing matricesxe2x80x9d and in U.S. Pat. No. 5,463,561 to Razdan entitled xe2x80x9cHigh Capacity Netlist Comparisonxe2x80x9d. The aforementioned patents solve the graph isomorphism problem for two netlists. They do not solve the sub-graph isomorphism problem or the inexact sub-graph isomorphism problem.
M. Ohlrich, C. Ebeling, et. al. at the University of Washington, in an article entitled xe2x80x9cSubGemini: Identifying SubCircuits using a Fast Subgraph Isomorphism Algorithmxe2x80x9d, 30th ACM/IEEE Design Automation Conference, 1993 IEEE, pp. 31-37, describe a solution to the exact sub-graph isomorphism problem for transistor-level netlists. It is a sub-circuit extraction technique entitled SubGemini which is an extension of Corneil""s graph isomorphism algorithm. The pattern and the main circuit design (master graph) are labeled alternately (rather than via explicit net comparison as will be described hereinafter in the detailed description of the invention). Labels are based on matched neighbors. Thus, if two nets or two devices have the same label, then a match is possible. It is not possible to extend the algorithm to compare labels for anything other than equality, and neither is there a method for matching two pattern nets to one master net, as is the case when the inputs are shorted together. Further, it is not possible for a pattern net to be matched to a master Vdd or GND net, since these must be provided with special labels in order to be identified as Vdd or GND. Therefore, SubGemini can perform only exact sub-graph pattern matching, requiring the user to enumerate all possible external net pattern variations, as shown in FIG. 2. In summary, SubGemini does not solve the inexact sub-graph isomorphism problem.
In U.S. Pat. No. 5,625,564 to Rogoyski entitled xe2x80x9cSystem and method for hierarchical device extractionxe2x80x9d devices are extracted from hierarchical shapes data. It uses rules instead of patterns. Its intent is to obtain devices from shapes and not sub-circuits from devices. Thus, it is not a general pattern matcher and does not perform inexact sub-graph isomorphism.
Z. Ling and D. Yun, in an article entitled xe2x80x9cAn Efficient Sub-Circuit Extraction Algorithm by Resource Managementxe2x80x9d, published in the Proceedings of Second International Conference on ASIC, Shanghai, P. R. China, 21-24 October 1996, describe an initial but fundamentally flawed solution for addressing the inexact sub-graph isomorphism problem. Referred to as the Generic Edge Unit-based Matching Algorithm, the technique defines isomorphism as any superset of the connectivity in the pattern. The worst-case time complexity, certainly imaginable when one considers the number of device connections which special nets such as Vdd and GND typically have, contains a factor d2n, wherein d is the maximal node degree in the main graph and n is the number of devices on the net in the sub-graph. This time complexity is caused by the pair-wise device adjacency edges which are used in place of hypergraph net nodes. The definition of isomorphism as any superset of the connectivity in the pattern is not a useful definition of isomorphism in transistor topologies because the user cannot constrain the number of transistors on internal nets, leading to false-positive matches. The algorithm cannot be extended to allow constraints on net connectivity because there is no explicit net node connectivity to be specified via pair-wise device adjacency edges. Ruling out these false matches is of exponential complexity and is not of practical use.
Based on an extensive search, no practical solution to the transistor-level inexact sub-graph isomorphism problem has, thus far, been found.
Accordingly, it is a primary object of the invention to provide a single pattern-matching algorithm which allows both exact and inexact pattern-matching so that transistor-level design automation tools can reliably perform transistor-level timing analysis, electrical rules checking, noise analysis, test pattern generation, design verification, and the like prior to manufacturing custom logic.
It is another object of the invention to allow a user (circuit designer) to specify which of each of the pattern external nets may be matched inexactly (attached to Vdd, attached to GND, or shorted to other external nets), and having the remainder of the pattern external net connections matched using exact isomorphism constraints.
It is still another object of the invention to achieve a substantial reduction in the number of patterns which circuit designers must generate, and altogether eliminate the need for an exponential number of patterns, by providing an inexact pattern matcher to a circuit designer.
It is yet another object of the invention to eliminate missed pattern instances in a circuit design, where the pattern is embedded such that its input(s) are attached to Vdd, attached to GND, or shorted to other inputs.
It is a further object of the invention to provide rooted sub-graph isomorphism so that a user can query whether a particular pattern is embedded at a particular location in the main circuit design, utilizing inexact sub-graph isomorphism.
The present invention solves both the exact and inexact sub-graph isomorphism problems for transistor-level netlists. Heretofore, only the exact pattern-matching problem has been solved efficiently. The goal in the invention is to quickly and efficiently identify sub-circuits from transistor-level designs via inexact sub-graph isomorphism.
The invention uses explicit net comparison to identify symmetry classes of nets which are potential matches. The members of each symmetry class are iterated over, using recursive calls to match the remainder of the pattern, and using backtracking to undo incorrect matches while exploring the entire solution space. Heuristics allow recursive calls in an optimal order to prevent an inherent worst-case exponential time for solving the sub-graph isomorphism problem.
According to the invention, a technique including a method of matching a pattern sub-circuit in a master circuit design is provided, the master circuit design being both formed by a plurality of master devices interconnected by master nets and modeled as a graph, and the pattern sub-circuit being formed by a plurality of pattern devices interconnected by pattern nets and modeled as a graph, wherein both nets and devices are explicitly modeled as nodes in the graphs, enabling both exact and inexact pattern matching using a single pattern matching engine, the method including the steps of: a) defining an explicit net comparison function that enables both the exact matching and the inexact matching of the pattern net to a master net, where an inexact match is a match to a master net which is connected to a power supply or to a net which is already matched to another pattern net; b) defining an explicit device comparison function that enables the exact matching of the pattern device to the master device based on a device characteristic; c) defining a node comparison function which compares two device nodes using the explicit device comparison function or compares two net nodes using the explicit net comparison function; d) identifying a pattern keynode; e) identifying a set of candidate nodes in the master circuit design for which a node comparison function is indicative of a potential match between the pattern keynode and a node in the master circuit design; f) iterating over the set of master candidate nodes; g) for each of the master candidate nodes exploring a potential match of the pattern in the master circuit design containing the candidate node, and h) repeating steps f) and g) until all instances of the pattern in the master circuit design have been identified.
Step g) further comprises the steps of: g1) matching the pattern node to the master node; g2) creating symmetry classes of device nodes and symmetry classes of net nodes connected to the nodes matched in step g1), where the symmetry class consists of a set of nodes comprising one pattern node and at least one master node which are potential matches; g3) identifying the symmetry classes which consist of exactly one pattern node and one master node and matching the pattern node to the master node for each of the identified symmetry classes; g4) using the node comparison function to identify the symmetry classes of nodes connected to the nodes matched in step g3); g5) repeating steps g3) and g4) until there are no symmetry classes which consist of exactly one unmatched pattern node and one master node; g6) selecting one symmetry class from all the symmetry classes which contain an unmatched pattern node; g7) iterating over the members of the symmetry class, exploring the potential match of the pattern node to each of the master nodes in the symmetry class: and g8) for each master node, making a recursive call with the initial match of the pattern node to the master node, and repeating steps g1) through g8) until either all pattern nodes have been matched to master nodes or a mismatch is found, prompting backtracking and unmatching nodes up to the symmetry class iteration in step g7).
Upon identification of each instance of the pattern, a user-supplied function is invoked to enable circuit design analysis, verification or optimization prior to its manufacture.